import java.util.*;
public class SecondChance{

LinkedList<String>list;
Scanner scanner;
int numberOfFrames,timeCounter,pageFaultCounter,clockPeriodCounter,clockPeriod;
LinkedList<SCNode>pageTable;
	public SecondChance(LinkedList<String>list,int clockPeriod,int numberOfFrames){
		pageTable= new LinkedList<SCNode>();
		this.numberOfFrames=numberOfFrames;
		this.list=list;
		System.out.println("Applying Second Chance for page replacement");
		System.out.println("RAM="+numberOfFrames+" page frames");
		System.out.println("Clock Period= "+clockPeriod+" page references");
		for(int i=0; i<numberOfFrames;i++){
			pageTable.add(new SCNode());
		}
		
		for(int i=1;i<list.size(); i++){
			String command = list.get(i);
			scanner=new Scanner(command);
			String letter=scanner.next();
			int pageNumber=scanner.nextInt();
			
			int inList=isInList(pageNumber);//check if the item page is already loaded
			if(inList!=-1){//if the page number is in the list generate in ram message
				 System.out.println(letter+" "+pageNumber+ ": in RAM");
				 pageTable.get(inList).RBIt=1;
			}
			else{//the page is not in ram check for an open slot
				int openSlot=findOPenSlot();
				if(openSlot!=-1){
					pageTable.get(openSlot).pageNumbner=pageNumber;
					pageTable.get(openSlot).loadTime=timeCounter++;
					System.out.println(letter+" "+pageNumber+ ": page fault");
					pageFaultCounter++;//count the number of page faults
				}
				else{//the ram is full lets evict a page
					int pageToEvict=pageToEvict();
					int temp=pageTable.get(pageToEvict).pageNumbner;
					pageTable.remove(pageToEvict);
					SCNode newPage=new SCNode();
					newPage.loadTime=timeCounter++;
					newPage.pageNumbner=pageNumber;
					pageTable.add(newPage);
					System.out.println(letter+" "+pageNumber+ ": page fault");
					pageFaultCounter++;//count the number of page faults
					System.out.println("  page "+temp +" evicted!");
				}
			}
			clockPeriodCounter++;
			if(clockPeriodCounter==clockPeriod){
				System.out.println("<<<Time to clear R bits>>>");
				clockPeriodCounter=0;
				clearRBits();
			}
		}
		System.out.println("Total number of page faults: "+pageFaultCounter);
	}
	private void clearRBits() {
		for(int i=0;i<pageTable.size();i++){
			pageTable.get(i).RBIt=0;
		}
	}
	private int pageToEvict() {
		boolean value=true;
		
		SCNode temp;
		for(int i=0;i<pageTable.size();i++){
			if(pageTable.get(i).RBIt==0)return i;
			else{//RBit is 1 set to zero but node at back of list
	         temp=pageTable.get(i);
	         pageTable.remove(i);
	         temp.RBIt=0;
	         temp.loadTime=timeCounter++;
	         pageTable.add(temp);
			}
		}
		return 0;
	}
	private int findOPenSlot() {
		
		for(int i=0;i<pageTable.size();i++){
			if(pageTable.get(i).pageNumbner==-1)return i;
		}
		return -1;
	}
	private int isInList(int pageNumber) {
		for(int i=0;i<pageTable.size();i++){
			if(pageTable.get(i).pageNumbner==pageNumber)return i;
		}
		return -1;
	}
}